package com.wish.algorithm.newCode;

import java.util.*;
import java.util.regex.Pattern;

/**
 * @Author: liu.cheng.su
 * @Time: 2022/10/11 0011 20:15
 * @Description: 记 2022年 10月 第一次 华为笔试 210 分
 */
public class Solution {

    public static void main(String[] args) {
        newEncrypt();
    }

    public static void newEncrypt() {
        Scanner in = new Scanner(System.in);
        String key = in.nextLine();
        String target = in.nextLine();
        String baseEng = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder builder = new StringBuilder();
        String newStr = "";
        //1 建立新的字母表
        //1.1 将单词秘钥 去重 保持顺序不变  遍历 拼接新的字符串 newStr，先判断 新的字符串是否
        //contains 当前字符，  false则加入拼接
        for (int i = 0; i < key.length(); i++) {
            if (!newStr.contains(String.valueOf(key.charAt(i)))) {
                newStr = builder.append(String.valueOf(key.charAt(i))).toString();
            }
        }
        //1.2 遍历 英文字母表 若存在于 newStr 则 replace 为"" 得到 eng_after
        int length = baseEng.length();
        String eng_after = baseEng;
        for (int i = 0; i < length; i++) {
            if (newStr.contains(String.valueOf(baseEng.charAt(i)))) {
                eng_after = eng_after.replace(String.valueOf(baseEng.charAt(i)), "");
            }
        }
        //1.3 newStr+eng_after 即为新的字母表
        String newBaseEng = newStr + eng_after;
        //2 根据原来字母表中的索引下标 找到新字母表下标下的 字符串 即为 加密后的字符串
        String outPut = "";
        for (int i = 0; i < target.length(); i++) {
            int index = baseEng.indexOf(target.charAt(i));
            outPut = outPut + newBaseEng.charAt(index);
        }
        System.out.println(outPut);
    }

    public static void integerToIP() {
        Scanner in = new Scanner(System.in);
        String ip = in.nextLine();
        String tenInt = in.nextLine();

        String[] ipArr = ip.split("\\.");
        int[] array = Arrays.stream(ipArr).mapToInt(Integer::parseInt).toArray();
        String binaryIp = "";
        String baseBinary = "00000000";
        String fullIpBinaryStr = baseBinary + baseBinary + baseBinary + baseBinary;
        for (int i : array) {
            String s = Integer.toBinaryString(i);
            s = baseBinary.substring(0, baseBinary.length() - s.length()) + s;
            binaryIp += s;
        }
        System.out.println(Long.parseLong(binaryIp, 2));

        String s2 = Long.toBinaryString(Long.parseLong(tenInt));
        s2 = fullIpBinaryStr.substring(0, fullIpBinaryStr.length() - s2.length()) + s2;

        String tenIp = "";
        for (int i = 0; i < s2.length(); i += 8) {
            String each = s2.substring(i, i + 8);
            each = binaryToTen(each);
            tenIp = tenIp + each + ".";
        }
        System.out.println(tenIp.substring(0, tenIp.length() - 1));
    }

    /**
     * 默认长度为8
     *
     * @param each
     * @return
     */
    private static String binaryToTen(String each) {
        int result = 0;
        for (int i = 0; i < 8; i++) {
            if (each.charAt(i) == '1') {
                result += 1 << (7 - i);
//                result += Math.pow(2,(7-i));
            }
        }
        return String.valueOf(result);
    }

    public static void getBeautyValue() {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        for (int i = 0; i < n; i++) {
            String s = in.nextLine();
            char[] chars = s.toCharArray();
            HashMap<Character, Integer> map = new HashMap<>();

            for (int i1 = 0; i1 < chars.length; i1++) {
                if (map.containsKey(s.charAt(i1))) {
                    map.put(s.charAt(i1), map.get(s.charAt(i1)) + 1);
                } else {
                    map.put(s.charAt(i1), 1);
                }
            }
            int[] arr = new int[map.size()];
            int index = 0;
            Iterator<Integer> iterator = map.values().iterator();
            while (iterator.hasNext()) {
                arr[index++] = iterator.next();
            }

            Arrays.sort(arr);
            int result = 0;
            int k = 0;
            for (int j = arr.length - 1; j >= 0; j--) {
                result += arr[j] * (26 - k++);
            }
            System.out.println(result);
        }
    }

    public static void getSubPassword() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        StringBuilder builder = new StringBuilder();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length() - 1; j > i + 1; j--) {
                String pw = s.substring(i, j + 1);
                StringBuilder passWord = builder.append(pw);
                String reversePW = passWord.reverse().toString();
                if (reversePW.equals(pw) && pw.length() > max) {
                    max = pw.length();
                }
                builder.delete(0, builder.length());
            }
        }
        System.out.println(max);
    }

    public static void brotherWord() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] str = s.split(" ");
        String target = str[str.length - 2];
        int k = Integer.parseInt(str[str.length - 1]);
        //查找 str 中 index [1-length-3] 的兄弟单词 存放到 List中 单词用,隔开
        List<String> list = new ArrayList<>();
        for (int i = 1; i < str.length - 2; i++) {
            if (isBrotherWord(target, str[i])) {
                list.add(str[i]);
            }
        }
        String[] arr = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (after(arr[i], arr[j])) {
                    String t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }

            }
        }
        System.out.println(arr.length);
        if (k - 1 <= arr.length - 1) {
            System.out.println(arr[k - 1]);
        }

    }

    /**
     * 字典排序 s在 s1 后面 则 return true
     * 默认 s s1 长度相同 且不相同
     *
     * @param s
     * @param s1
     * @return
     */
    private static boolean after(String s, String s1) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) > s1.charAt(i)) {
                return true;
            } else if (s.charAt(i) < s1.charAt(i)) {
                return false;
            }
        }
        return false;
    }

    private static boolean isBrotherWord(String a, String b) {
        if (a.equals(b)) {
            return false;
        }
        String aAfterSort = sortStr(a);
        String bAfterSort = sortStr(b);
        if (aAfterSort.equals(bAfterSort)) {
            return true;
        }
        return false;
    }

    private static String sortStr(String a) {
        char[] chars = a.toCharArray();
        for (int i = 0; i < chars.length - 1; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] > chars[j]) {
                    char t = chars[i];
                    chars[i] = chars[j];
                    chars[j] = t;
                }
            }
        }
        return String.valueOf(chars);
    }

    public static void AjMath() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            String[] split = s.split("/");

            Float i = Float.valueOf(split[0]);
            Float j = Float.valueOf(split[1]);
            StringBuilder builder = new StringBuilder();
            float f = 0f;
            float y = 2f;
            while (true) {
                if (1f / y == (i / j)) {
                    System.out.println("1/" + (int) y);
                    return;
                } else if (1f / y > (i / j)) {
                    y += 1f;
                } else {
                    break;
                }
            }
            while (true) {
                if (f == (i / j)) {
                    break;
                }
                if (f + 1f / y > (i / j)) {
                    y++;
                    continue;
                }
                f += 1f / y;
                builder.append("1/" + (int) y + "+");
                y++;
            }
            System.out.println(builder.toString().substring(0, builder.length() - 1));
        }
    }

    /**
     * 求出最长的连续 字符串
     * abcd12345ed125ss123058789
     * a8a72a6a5yy98y65ee1r2
     */
    public static void findLongSubNumStr() {
        Scanner in = new Scanner(System.in);
        String numStr = "0123456789";
        while (in.hasNextLine()) {
            String s = in.nextLine();
            List<String> list = new ArrayList<>();
            int j = 0;
            int maxLength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (numStr.contains(String.valueOf(s.charAt(i)))) {
                    j = i;
                    while (numStr.contains(String.valueOf(s.charAt(j)))) {
                        if (j == s.length() - 1) {
                            j++;
                            break;
                        }
                        j++;
                    }
                    if (j - i > maxLength) {
                        maxLength = j - i;
                        list.clear();
                        list.add(s.substring(i, j));
                    } else if (j - i == maxLength) {
                        list.add(s.substring(i, j));
                    }
                    i = j;
                }
            }
            StringBuilder builder = new StringBuilder();
            for (String s1 : list) {
                builder.append(s1);
            }
            System.out.println(builder + "," + maxLength);
        }

    }

    static Pattern E = Pattern.compile("[A-Z]");
    static Pattern e = Pattern.compile("[a-z]");
    static Pattern num = Pattern.compile("[0-9]");

    public static void pw() {
        Scanner in = new Scanner(System.in);
        String encrypt = in.nextLine();
        String decode = in.nextLine();
        StringBuilder eBuilder = new StringBuilder();
        StringBuilder dBuilder = new StringBuilder();

        for (int i = 0; i < encrypt.length(); i++) {
            eBuilder.append(encrypt(encrypt.charAt(i)));
        }
        for (int i = 0; i < decode.length(); i++) {
            dBuilder.append(decode(decode.charAt(i)));
        }
        System.out.println(eBuilder);
        System.out.println(dBuilder);
    }

    private static char decode(char c) {
        String s = String.valueOf(c);
        if (E.matcher(s).find()) {
            if (s.equals("A")) {
                return 'z';
            }
            return (char) (s.toLowerCase().charAt(0) - 1);
        }
        if (e.matcher(s).find()) {
            if (s.equals("a")) {
                return 'Z';
            }
            return (char) (s.toUpperCase().charAt(0) - 1);
        }
        if (num.matcher(s).find()) {
            int i = Integer.parseInt(s);
            if (i == 0) {
                return '9';
            } else {
                return String.valueOf(i - 1).charAt(0);
            }
        }
        return '*';
    }

    private static char encrypt(char c) {
        String s = String.valueOf(c);
        if (E.matcher(s).find()) {
            if (s.equals("Z")) {
                return 'a';
            }
            return (char) (s.toLowerCase().charAt(0) + 1);
        }
        if (e.matcher(s).find()) {
            if (s.equals("z")) {
                return 'A';
            }
            return (char) (s.toUpperCase().charAt(0) + 1);
        }
        if (num.matcher(s).find()) {
            int i = Integer.parseInt(s);
            if (i == 9) {
                return '0';
            }
            return String.valueOf(i + 1).charAt(0);

        }
        return '*';
    }

    public static void checkIPV4() {
        String N = "NO";
        String Y = "YES";

        Scanner in = new Scanner(System.in);
        Pattern compile = Pattern.compile("[0-9]");
        String s = in.nextLine();
        String[] split = s.split("\\.");
        if (split.length != 4) {
            System.out.print(N);
            return;
        }
        for (String s1 : split) {
            if (s1.length() == 0) {
                System.out.print(N);
                return;
            }
            boolean b = !compile.matcher(String.valueOf(s1.charAt(0))).find();
            if (b || (s1.length() != 1 && s1.startsWith("0"))) {
                System.out.print(N);
                return;
            }
        }
        int[] array = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > 255) {
                System.out.print(N);
                return;
            }
        }
        System.out.print(Y);
    }

    /**
     * 英文字母 a-z 不区分大小写
     * 出现大小写字母，按照输入顺序排列
     * 非英文字母  保持原来的位置
     */
    public static void advancedEngSort() {
        Scanner in = new Scanner(System.in);
        String inputStr = in.nextLine();
        char[] inputStrChars = inputStr.toCharArray();
        //遍历字符串 count 字母个数 用于建立数组长度
        int n = 0;
        for (int i = 0; i < inputStrChars.length; i++) {
            if ((inputStrChars[i] >= 'A' && inputStrChars[i] <= 'Z') || (inputStrChars[i] >= 'a' && inputStrChars[i] <= 'z')) {
                n++;
            }
        }
        //new 数组 长度相同 一个存放 char 另一个存放对应的 index 并对分别排序  !bBaAA^8hbb
        char[] cArr = new char[n];
        int[] iArr = new int[n];
        int index = 0;
        for (int i = 0; i < inputStrChars.length; i++) {
            if ((inputStrChars[i] >= 'A' && inputStrChars[i] <= 'Z') || (inputStrChars[i] >= 'a' && inputStrChars[i] <= 'z')) {
                cArr[index] = inputStrChars[i];
                iArr[index] = i;
                index++;
            }
        }
        for (int i = 0; i < cArr.length - 1; i++) {
            for (int j = i + 1; j < cArr.length; j++) {
                char charI = String.valueOf(cArr[i]).toLowerCase().charAt(0);
                char charJ = String.valueOf(cArr[j]).toLowerCase().charAt(0);
                if (charI > charJ) {
                    char t = cArr[j];
                    //将 j 前面 i后面 所有元素向后移动一位 将j的元素 替换 i的元素
                    for (int k = j; k > i; k--) {
                        cArr[k] = cArr[k - 1];
                    }
                    cArr[i] = t;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            inputStrChars[iArr[i]] = cArr[i];
        }

        System.out.println(String.valueOf(inputStrChars));
    }


    public static void listSinger() {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        String[] s1 = s.split(" ");

        int[] array = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();

        //假设 除两边 数据 中间每个数据作为 最高数 的时候 最长子序列的 去除数 个数集合
        List<Integer> result_list = new ArrayList<>();
        for (int i = 1; i < array.length - 1; i++) {
            int[] left = new int[i + 1];
            int[] right = new int[array.length - i];

            //左侧 最长 递增 子序列
            for (int j = 0; j <= i; j++) {
                left[j] = array[j];
            }
            //右侧 最长 递增（逆序） 子序列
            int index = 0;
            for (int j = array.length - 1; j >= i; j--) {
                right[index] = array[j];
                index++;
            }
            int i1 = maximumSubList(left);
            int i2 = maximumSubList(right);
            result_list.add(array.length - i1 - i2 + 1);
        }

        Collections.sort(result_list);
        System.out.println(result_list.get(0));

    }

    /**
     * 通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
     * https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4?tpId=37&tqId=21247&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=undefined&tags=&title=
     * 复杂度太大 修正
     */
    public static void listSingerDeprecate() {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        String[] s1 = s.split(" ");
        int[] array = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();

        //假设 除两边 数据 中间每个数据作为 最高数 的时候 最长子序列的 去除数 个数集合
        List<Integer> result_list = new ArrayList<>();
        for (int i = 1; i < array.length - 1; i++) {
            int[] left = new int[i + 1];
            int[] right = new int[array.length - i];

            //左侧 最长 递增 子序列
            for (int j = 0; j <= i; j++) {
                left[j] = array[j];
            }
            //右侧 最长 递增（逆序） 子序列
            int index = 0;
            for (int j = array.length - 1; j >= i; j--) {
                right[index] = array[j];
                index++;
            }
            int i1 = maximumSubList(left);
            int i2 = maximumSubList(right);
            result_list.add(array.length - i1 - i2 + 1);
        }

        Collections.sort(result_list);
        System.out.println(result_list.get(0));

    }

    private static int maximumSubList(int[] arr) {
        int[] temp = new int[arr.length];
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    temp[i] = Math.max(temp[j] + 1, temp[i]);
                }
            }
        }
        Arrays.sort(temp);
        return temp[temp.length - 1] + 1;
    }

    public static void average() {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String s = in.nextLine();
        String[] s1 = s.split(" ");
        int[] array = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();

        List<Integer> list = new ArrayList<>();
        int count = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0) {
                count++;
            }
            if (array[i] > 0) {
                list.add(array[i]);
            }
        }
        System.out.print(count + " ");
        if (list.size() == 0) {
            System.out.println("0.0");
            return;
        }

        double sum = 0.0;
        for (Integer integer : list) {
            sum += integer;
        }
        System.out.printf("%.1f\n", sum / list.size());
    }

    /**
     * 自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376
     */
    public static void ziShou() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int count = 0;
        for (int i = 0; i <= n; i++) {
            String mul = String.valueOf(i * i);
            String s = String.valueOf(i);
            if (mul.lastIndexOf(s) == mul.length() - s.length()) {
                count++;
            }
        }
        System.out.println(count);
    }

    /**
     * 等差数列 2，5，8，11，14。。。
     */
    public static void arithmeticProgression() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println((3 * n + 1) * n / 2);
    }

    public static void sortNums() {
        Scanner in = new Scanner(System.in);
        Integer.parseInt(in.nextLine());

        String s = in.nextLine();
        String[] s1 = s.split(" ");

        int[] array = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(array);
        int n = Integer.parseInt(in.nextLine());
        if (n == 0) {
            for (int i = 0; i < array.length; i++) {
                if (i == array.length - 1) {
                    System.out.print(array[i]);
                } else {
                    System.out.print(array[i] + " ");
                }
            }
        } else {
            for (int i = array.length - 1; i >= 0; i--) {
                if (i == 0) {
                    System.out.print(array[i]);
                } else {
                    System.out.print(array[i] + " ");
                }
            }
        }
    }

    public static void countCharMaximum() {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();

        char[] chars = line.toCharArray();
        for (int i = 0; i < chars.length - 1; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] > chars[j]) {
                    char temp = chars[i];
                    chars[i] = chars[j];
                    chars[j] = temp;
                }
            }
        }

        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                map.put(chars[i], map.get(chars[i]) + 1);
            } else {
                map.put(chars[i], 1);
            }
        }
        StringBuilder builder = new StringBuilder();
        Collection<Integer> values = map.values();
        ArrayList<Integer> list = new ArrayList<>();
        Iterator<Integer> iterator = values.iterator();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        Collections.sort(list);

        for (int i = list.size() - 1; i >= 0; i--) {
            for (int j = 0; j < chars.length; j++) {
                if (map.get(chars[j]) == list.get(i)) {
                    if (builder.toString().contains(String.valueOf(chars[j]))) {
                        continue;
                    }
                    builder.append(chars[j]);
                }
            }
        }
        System.out.println(builder);
    }

    public static void maxSubList() {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());

        int[] temp = new int[n];
        String s = in.nextLine();
        String[] s1 = s.split(" ");
        int[] arr = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    temp[i] = Math.max(temp[i], temp[j] + 1);
                }
            }
        }
        Arrays.sort(temp);
        System.out.println(temp[n - 1] + 1);
    }

    public static void average2() {
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        int count = 0;
        while (in.hasNextInt()) {
            int i = in.nextInt();
            if (i >= 0) {
                list.add(i);
            }
            count++;
        }
        System.out.println(count - list.size());
        if (list.size() == 0) {
            System.out.println("0.0");
        } else {
            double sum = 0;
            for (Integer integer : list) {
                sum += integer;
            }
            System.out.printf("%.1f\n", sum / list.size());
        }
    }

    /**
     * 可以同时整除 i j
     */
    public static void getMinMutNumber2() {
        Scanner in = new Scanner(System.in);
        int i = in.nextInt();
        int j = in.nextInt();

        int c = Math.max(i, j);
        while (true) {
            if (c % i == 0 && c % j == 0) {
                break;
            }
            c++;
        }
        System.out.println(c);
    }

    public static void getMinMutNumber() {
        Scanner in = new Scanner(System.in);
        int i = in.nextInt();
        int j = in.nextInt();
        System.out.println(i * j / methods(i, j));
    }

    /**
     * 得到 最大公约数
     */
    private static int methods(int i, int j) {
        if (i == j) {
            return i;
        }
        return i > j ? methods((i - j), j) : methods((j - i), i);
    }

    public static void reverseStr() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;
        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
        System.out.println(String.valueOf(chars));
    }

    private static void getNodeKey() {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int num = scan.nextInt();
            ListNode header = new ListNode();
            for (int i = 0; i < num; i++) {
                int value = scan.nextInt();
                ListNode node = new ListNode(value, header.next);
                header.next = node;
            }
            int target = scan.nextInt();
            for (int i = 0; i < target; i++) {
                header = header.next;
            }
            System.out.println(header.value);
        }
    }

    static class ListNode {
        int value;
        ListNode next;

        public ListNode() {

        }

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }


    public static void countDifferentChar() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        Pattern eng = Pattern.compile("[a-zA-Z]");
        Pattern num = Pattern.compile("[0-9]");
        String blank = " ";

        int eng_count = 0, blank_count = 0, num_count = 0, other_count = 0;
        for (int i = 0; i < s.length(); i++) {
            String each = String.valueOf(s.charAt(i));
            if (eng.matcher(each).find()) {
                eng_count++;
            } else if (num.matcher(each).find()) {
                num_count++;
            } else if (blank.equals(each)) {
                blank_count++;
            } else {
                other_count++;
            }
        }
        System.out.println(eng_count);
        System.out.println(blank_count);
        System.out.println(num_count);
        System.out.println(other_count);
    }

    public static void snakeMatrix() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int[][] matrix = new int[n][n];
        int k = 0;
        int index = 1;
        while (k <= n - 1) {
            int i = k;
            int j = 0;
            while (i >= 0) {
                matrix[i][j] = index;
                i--;
                j++;
                index++;
            }
            k++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    break;
                }
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void handlePic() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length - 1; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] > chars[j]) {
                    char t = chars[i];
                    chars[i] = chars[j];
                    chars[j] = t;
                }
            }
        }
        System.out.println(String.valueOf(chars));
    }

    /**
     * 最长递增子序列 动态规划
     *
     * @param nums
     */
    public static int maxIncreaseSubList(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int ret = 1;
        for (int i = 0; i < dp.length; i++) {
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }


    /**
     * N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
     * 通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
     * <p>
     * 思路：
     * 将 任意一个同学作为中间最高的人，算出此时需要出列的 人数 temp     左边递增 右边递减
     * 将 temp 给到 list
     * 算出 list 中的最小值
     */
    public static void singQueue() {
        Scanner in = new Scanner(System.in);
        int all = Integer.parseInt(in.nextLine());
        int[] queue = new int[all];

        String s = in.nextLine();
        String[] s1 = s.split(" ");
        for (int i = 0; i < all; i++) {
            queue[i] = Integer.parseInt(s1[i]);
        }


        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < queue.length - 1; i++) {
            int[] left = new int[i];
            int[] right = new int[queue.length - i - 1];
            //i左侧递增 顺序遍历 最长子序列
            for (int j = 0; j < i; j++) {
                left[j] = queue[j];
            }
            //i右侧递减 逆序遍历 最长子序列
            for (int k = queue.length - 1; k > i; k--) {
                right[k - i - 1] = queue[k];
            }
            int i1 = maxIncreaseSubList(left);
            int i2 = maxIncreaseSubList(right);
            list.add(queue.length - i1 - i2 - 1);
        }

        int min = all;
        for (Integer integer : list) {
            if (integer < min) {
                min = integer;
            }
        }
        System.out.print(min);
    }

    public static void reverseChars() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        Pattern pattern = Pattern.compile("[a-zA-Z]");
        for (int i = 0; i < s.length(); i++) {
            if (!pattern.matcher(String.valueOf(s.charAt(i))).find()) {
                s = s.replace(String.valueOf(s.charAt(i)), " ");
            }
        }
        String[] s1 = s.split(" ");
        int i = 0;
        int j = s1.length - 1;
        while (i < j) {
            String temp = s1[i];
            s1[i] = s1[j];
            s1[j] = temp;
            i++;
            j--;
        }
        for (int i1 = 0; i1 < s1.length; i1++) {
            if (i1 == s1.length - 1) {
                System.out.print(s1[i1]);
            } else {
                System.out.print(s1[i1] + " ");
            }
        }
    }

    /**
     * 删除字符串中出现最少的单词
     */
    public static void removeChar() {
        Scanner in = new Scanner(System.in);
        String next = in.next();
        Map<Character, Integer> map = new HashMap<>();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < next.length(); i++) {
            if (map.containsKey(next.charAt(i))) {
                map.put(next.charAt(i), map.get(next.charAt(i)) + 1);
            } else {
                map.put(next.charAt(i), 1);
            }
        }

        Collection<Integer> values = map.values();
        Set<Character> characters = map.keySet();

        int min = 21;
        Iterator<Integer> v_iterator = values.iterator();
        while (v_iterator.hasNext()) {
            Integer next1 = v_iterator.next();
            if (next1 < min) {
                min = next1;
            }
        }

        Iterator<Character> k_iterator = characters.iterator();
        while (k_iterator.hasNext()) {
            Character currentKey = k_iterator.next();
            if (map.get(currentKey) == min) {
                list.add(currentKey);
            }
        }
        StringBuilder builder = new StringBuilder();
        ;
        String r = next;
        for (Character character : list) {
            for (int i = 0; i < r.length(); i++) {
                if (character != r.charAt(i)) {
                    builder.append(r.charAt(i));
                }
            }
            r = builder.toString();
            builder = new StringBuilder();
        }
        System.out.println(r);
    }


    public static void removeChar2() {
        Scanner in = new Scanner(System.in);
        String next = in.next();
        Map<Character, Integer> map = new HashMap<>();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < next.length(); i++) {
            if (map.containsKey(next.charAt(i))) {
                map.put(next.charAt(i), map.get(next.charAt(i)) + 1);
            } else {
                map.put(next.charAt(i), 1);
            }
        }

        Collection<Integer> values = map.values();
        Integer min = Collections.min(values);

        for (Character c : map.keySet()) {
            if (map.get(c) == min) {
                next = next.replaceAll(String.valueOf(c), "");
            }
        }
        System.out.println(next);
    }


    public static void bottle() {
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (true) {
            int next = in.nextInt();
            if (next == 0) {
                break;
            }
            list.add(next / 2);
        }
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

    public static void simplePassWord() {
        HashMap<Character, Integer> baseMap = new HashMap<>();
        baseMap.put('a', 2);
        baseMap.put('b', 2);
        baseMap.put('c', 2);
        baseMap.put('d', 3);
        baseMap.put('e', 3);
        baseMap.put('f', 3);
        baseMap.put('g', 4);
        baseMap.put('h', 4);
        baseMap.put('i', 4);
        baseMap.put('j', 5);
        baseMap.put('k', 5);
        baseMap.put('l', 5);
        baseMap.put('m', 6);
        baseMap.put('n', 6);
        baseMap.put('o', 6);
        baseMap.put('p', 7);
        baseMap.put('q', 7);
        baseMap.put('r', 7);
        baseMap.put('s', 7);
        baseMap.put('t', 8);
        baseMap.put('u', 8);
        baseMap.put('v', 8);
        baseMap.put('w', 9);
        baseMap.put('x', 9);
        baseMap.put('y', 9);
        baseMap.put('z', 9);
        StringBuilder builder = new StringBuilder();
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        for (int i = 0; i < s.length(); i++) {
            if (baseMap.containsKey(s.charAt(i))) {
                builder.append(baseMap.get(s.charAt(i)));
            } else if ("0123456789".contains(String.valueOf(s.charAt(i)))) {
                builder.append(s.charAt(i));
            } else {
                if (s.charAt(i) == 'Z') {
                    builder.append('a');
                } else {
                    builder.append(String.valueOf((char) (s.charAt(i) + 1)).toLowerCase());
                }
            }
        }

        System.out.println(builder);
    }

    // 校验是否有重复子串
    private static boolean getString(String str, int l, int r) {
        if (r >= str.length()) {
            return false;
        }
        if (str.substring(r).contains(str.substring(l, r))) {
            return true;
        } else {
            return getString(str, l + 1, r + 1);
        }
    }

    // 检查是否满足正则
    private static boolean getMatch(String str) {
        int count = 0;
        Pattern p1 = Pattern.compile("[A-Z]");
        if (p1.matcher(str).find()) {
            count++;
        }
        Pattern p2 = Pattern.compile("[a-z]");
        if (p2.matcher(str).find()) {
            count++;
        }
        Pattern p3 = Pattern.compile("[0-9]");
        if (p3.matcher(str).find()) {
            count++;
        }
        Pattern p4 = Pattern.compile("[^a-zA-Z0-9]");
        if (p4.matcher(str).find()) {
            count++;
        }
        if (count >= 3) {
            return false;
        } else {
            return true;
        }
    }

    /**
     * 输入一个 int 型的正整数，计算出该 int 型数据在内存中存储时 1 的个数。
     */
    public static void count1nums() {
        Scanner in = new Scanner(System.in);
        int i = in.nextInt();
        int count = 0;
        for (int j = 31; j >= 0; j--) {
            if ((i & 1) == 1) {
                count++;
            }
            i = i >> 1;
        }
        System.out.println(count);
    }


    public static void sortWords() {
        Scanner in = new Scanner(System.in);
        int num = Integer.parseInt(in.nextLine());
        String[] strArr = new String[num];
        for (int i = 0; i < num; i++) {
            strArr[i] = in.nextLine();
        }
        for (int i = 0; i < strArr.length - 1; i++) {
            for (int j = i + 1; j < strArr.length; j++) {
                boolean judge = needChange(strArr[i], strArr[j]);
                if (judge) {
                    String temp = strArr[i];
                    strArr[i] = strArr[j];
                    strArr[j] = temp;
                }
            }
        }
        for (String s : strArr) {
            System.out.println(s);
        }
    }

    /**
     * s before t return false means need change index
     *
     * @param s
     * @param t
     * @return
     */
    private static boolean needChange(String s, String t) {
        int num = Math.min(s.length(), t.length());
        for (int i = 0; i < num; i++) {
            if (s.charAt(i) > t.charAt(i)) {
                return true;
            } else if (s.charAt(i) < t.charAt(i)) {
                return false;
            }
        }
        return s.length() > t.length();
    }


    public static void reverseWord() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] s1 = s.split(" ");
        int i = 0;
        int j = s1.length - 1;

        while (i < j) {
            String temp = s1[i];
            s1[i] = s1[j];
            s1[j] = temp;
            i++;
            j--;
        }
        for (int i1 = 0; i1 < s1.length; i1++) {
            if (i1 == s1.length - 1) {
                System.out.print(s1[i1]);
            } else {
                System.out.print(s1[i1] + " ");
            }
        }
    }

    public static void reverseNum() {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        char[] chars = s.toCharArray();
        int i = 0;
        int j = chars.length - 1;

        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
        System.out.println(String.valueOf(chars));
    }

    public static void dropMutChar() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        Set<Character> set = new HashSet<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            set.add(s.charAt(i));
        }
        System.out.println(set.size());
    }

    /**
     * 输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。
     * 保证输入的整数最后一位不是 0 。
     */
    public static void getInt2() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        StringBuilder builder = new StringBuilder();

        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (builder.indexOf(String.valueOf(c)) == -1) {
                builder.append(c);
            }
        }
        System.out.println(builder);
    }

    public static void mergeTableDate() {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        Map<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            String line = in.nextLine();

            String[] s = line.split(" ");
            int key = Integer.parseInt(s[0]);
            int value = Integer.parseInt(s[1]);

            if (map.containsKey(key)) {
                map.put(key, map.get(key) + value);
            } else {
                map.put(key, value);
            }
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            System.out.println(next.getKey() + " " + next.getValue());
        }
    }

    /**
     * 取整
     */
    public static void getInt() {
        Scanner in = new Scanner(System.in);
        double d = in.nextDouble();
        long round = Math.round(d);
        System.out.println(round);
    }


    /**
     * 递归过于复杂
     */
    public static void doGetPrimer() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        long num = Long.parseLong(s);
        getPrimer(num);
    }

    /**
     * 输入一个正整数，按照从小到大的顺序输出它的所有质因子
     */
    private static void getPrimer(long num) {
        for (int i = 2; i <= num; i++) {
            if (num % i == 0) {
                System.out.print(i + " ");
                getPrimer(num / i);
                break;
            }
            if (i == num) {
                System.out.print(i + "");
            }
        }
    }


    /**
     * 十六进制 ->十进制
     */
    public static void decimalConversion() {
        Scanner in = new Scanner(System.in);
        String numOx = in.nextLine();
        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 10);
        map.put('B', 11);
        map.put('C', 12);
        map.put('D', 13);
        map.put('E', 14);
        map.put('F', 15);
        String base = "1234567890";
        int result = 0;

        String substring = numOx.substring(2);
        int length = substring.length();
        for (int i = 0; i < length; i++) {
            int m = (int) Math.pow(16, (length - i) - 1);
            if (base.contains(String.valueOf(substring.charAt(i)))) {
                int temp = Integer.parseInt(String.valueOf(substring.charAt(i))) * m;
                result += temp;
            } else {
                //A B C D E F -> 11 12 13 14 15 16
                int temp2 = map.get(substring.charAt(i)) * m;
                result += temp2;
            }
        }

        System.out.println(result);
    }

    public static void decimalConversion2() {
        Scanner in = new Scanner(System.in);
        String numOx = in.nextLine();
        System.out.println(Integer.parseInt(numOx.substring(2), 16));
    }

    /**
     * 将 字符串 每八个字符输出
     */
    public static void splitStringEach8Length() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        int l = s.length() / 8;

        for (int i = 0; i < l; i++) {
            System.out.println(s.substring(8 * i, 8 * i + 8));
        }
        String substring = s.substring(l * 8);
        String raw = "00000000";
        if (substring.length() < 8 && substring.length() > 0) {
//            raw = substring + raw.substring(substring.length());
            System.out.println(raw.replaceFirst(raw.substring(0, substring.length()), substring));
//            System.out.println(raw);
        }
        in.close();
    }

    /**
     * 排序算法
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quicksort(int[] arr, int left, int right) {
        if (right >= left) {
            //保存基数
            int basic = arr[left];
            //定义左右指针
            int i = left;
            int j = right;
            while (i < j) {        //左指针小于右指针
                while (i < j && arr[j] > basic) {//操作右指针找到小于基数的下标
                    j--;
                }
                if (i < j) {
                    arr[i] = arr[j];    //将右指针对应小于基数的值放到左指针所指的位置
                    i++;                //左指针自加
                }
                while (i < j && arr[i] < basic) {//相反，找到大于基数的下标
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i];    //大于基数的值赋给右指针所指的位置
                    j--;                //右指针自减
                }
            }
            arr[i] = basic;                //将基数放入到指针重合处
            quicksort(arr, left, i - 1);    //重复调用，对左半部分数组进行排序
            quicksort(arr, i + 1, right);    //对右半部分数组进行排序
        }
    }

    public static void bSort() {
        int[] a = {1, 3, 5, 0, 6, 2, 9, 4};
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        System.out.println(a);
    }

    /**
     * 去重随机数并 升序输出
     */
    public static void MingMingRandomNumber() {
        Scanner in = new Scanner(System.in);
        Set<Integer> set = new HashSet<>();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            set.add(num);
        }
        List<Integer> list = new ArrayList<>(set);
        list.sort(null);
        for (Integer i : list) {
            System.out.println(i);
        }
    }

    /**
     * 计算某个char  在String中出现的次数
     */
    public static void countChar() {
        Scanner in = new Scanner(System.in);
        in.useDelimiter("\n");
        String str = in.next();
        String ch = in.next();
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (String.valueOf(str.charAt(i)).equalsIgnoreCase(ch)) {
                count++;
            }
        }
        System.out.println(count);
        in.close();
    }

    /**
     * 计算最后一个单词的长度
     */
    public static void countLastWord() {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        in.useDelimiter("\n");
        String a = in.next();
        int i = a.lastIndexOf(" ");
        System.out.println(a.length() - i - 1);
    }

    public static int[][] generateMatrix2(int n) {
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, button = n - 1, index = 1, lastNum = n * n;
        while (index <= lastNum) {
            // 左到右
            for (int i = left; i <= right; i++) {
                matrix[top][i] = index++;
            }
            top++;

            //上到下
            for (int i = top; i <= button; i++) {
                matrix[i][right] = index++;
            }
            right--;

            //右到左
            for (int i = right; i >= left; i--) {
                matrix[button][i] = index++;
            }
            button--;
            //下到上
            for (int i = button; i >= top; i--) {
                matrix[i][left] = index++;
            }
            left++;
        }

        return matrix;
    }

    /**
     * 顺时针 生成二维数组
     *
     * @param n
     * @return
     */
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        //定义四个指针
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        //定义第一个数和最后一个数
        int num = 1, target = n * n;
        while (num <= target) {
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            } //从左到右
            top++;
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            } //从上到下
            right--;
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            } //从右到左
            bottom--;
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            } //从下到上
            left++;
        }
        return matrix;
    }

    /**
     * 判断子序列
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence(String s, String t) {
        //双指针法
        int sLength = s.length();
        int tLength = t.length();
        int i = 0;
        int j = 0;
        while (i < sLength && j < tLength) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == sLength;
    }

    /**
     * 翻转前缀字符串
     *
     * @param word
     * @param ch
     * @return
     */
    public static String reversePrefix(String word, char ch) {
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < word.length()) {
            if (Objects.equals(word.charAt(i), ch)) {
                k = i;
                break;
            }
            i++;
        }
        char[] chars = word.toCharArray();
        while (j < k) {
            char temp = chars[j];
            chars[j++] = chars[k];
            chars[k--] = temp;
        }
        return String.valueOf(chars);
    }
}
